#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

  /*Definition for singly-linked list.*/
  struct ListNode {
      int val;
      struct ListNode *next;
  };
 

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
    ListNode* smallhead, * smalltail;
    ListNode* greathead, * greattail;
    smallhead = smalltail = (ListNode*)malloc(sizeof(ListNode));
    greathead = greattail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur = head;
    while (pcur)
    {
        if (pcur->val < x)
        {
            smalltail->next = pcur;
            smalltail = smalltail->next;

        }
        else
        {
            greattail->next = pcur;
            greattail = greattail->next;

        }
        pcur = pcur->next;
    }

    greattail->next = NULL;
    smalltail->next = greathead->next;
    ListNode* ret = smallhead->next;
    free(smallhead);
    free(greathead);
    smallhead = greattail = NULL;

    return ret;

}